package com.example.leetcode.tree;

import com.example.leetcode.tree.common.TreeNode;
import com.example.leetcode.tree.common.TreeUtils;

import java.util.*;


public class leetcode508 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        Integer[] nums = {1};
        System.out.println(Arrays.toString(solution.findFrequentTreeSum(TreeUtils.generateLeetcodeTree(nums))));
    }


    static class Solution {
        private final Map<Integer, Integer> freqMap = new HashMap<>();
        private int maxFreq = 0;

        public int[] findFrequentTreeSum(TreeNode root) {
            postOrder(root);

            List<Integer> res = new ArrayList<>();
            for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
                if (entry.getValue() == maxFreq) {
                    res.add(entry.getKey());
                }
            }

            return res.stream().mapToInt(i -> i).toArray();
        }

        private int postOrder(TreeNode node) {
            if (node == null) return 0;

            int leftSum = postOrder(node.left);
            int rightSum = postOrder(node.right);
            int sum = node.val + leftSum + rightSum;

            freqMap.put(sum, freqMap.getOrDefault(sum, 0) + 1);
            maxFreq = Math.max(maxFreq, freqMap.get(sum));

            return sum;
        }
    }


}
